package code;
public class 剑指offer11 {

    public int minArray(int[] numbers) {
        /***
         * 1、分治思想：
         * 首先本题的问题在于找到最小值，而如果直接去查找最小值就忽视了数组原本的特殊性。
         * 这个数组有什么特殊？其实我们需要找到这个旋转点，这个旋转点就是最小值。而旋转点的性质就是：
         * 旋转点之前的值是>=旋转点，而旋转点之后的值是<=旋转点。
         * 但是旋转点是未知的，不过我们发现：
         * 而之前的点>=第一个数，之后的点<=第一个数。设这个常量为const，但是我们观察另一个问题，有种模糊的情况会发生。
         * 其实很容易想到去分治，假设我们随机查询一个点，其值为value，那么面临三种可能的情况：
         * 1、value>const：为右序列
         * 2、value<const: 为左序列
         * 3、value=const: 可能为左，可能为右。其实我们无法知道属于哪方。可以将[left,right]问题->[left+1,right]这样是等价的。
         * 为什么可以这样做？其实只需说明left这个点是不是旋转点都无所谓。
         * 1、left是旋转点：但是value保留了旋转点的值。但是我们的旋转点还能找到吗。因为left是旋转点，那么value替代为旋转点。
         * 2、left不是旋转点，那无需考虑，
         * const更新为left+1的值
         */
        int left=0,right=numbers.length-1;
        int MIN=numbers[left];
        while(left<right){
            if(numbers[left]==numbers[right]){left++;right--;}
            else break;
        }
        int value=numbers[left];
        while(left<right){
            int mid=(left+right)/2;
            if(numbers[mid]>=value)left=mid+1;
            else{
                right=mid;
            }
        }
        return Math.min(MIN,Math.min(numbers[left],value));


    }
    public static void main(String[] args) {

    }
}
